package com.mdnote.practice.sort;

import org.junit.Assert;
import org.junit.Test;

import java.util.*;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/11/14 9:35
 * @Email rhythm_2019@163.com
 * @Description 1122. 数组的相对排序
 */
public class LeetCode1122 {

    public int[] relativeSortArray_s1(int[] arr1, int[] arr2) {

        if (arr1 == null || arr2 == null || arr1.length == 0) {
            return new int[0];
        }

        List<Integer> arr1List = new ArrayList<>();
        for (int i = 0; i < arr1.length; i++) {
            arr1List.add(arr1[i]);
        }

        HashMap<Integer, Integer> arr2Map = new HashMap<>();
        for (int i = 0; i < arr2.length; i++) {
            arr2Map.put(arr2[i], i);
        }

        arr1List.sort((o1, o2) -> {
            Integer o1Int = arr2Map.get(o1);
            Integer o2Int = arr2Map.get(o2);

            if (o1Int != null && o2Int != null) {
                return o1Int - o2Int;
            } else if (o1Int == null && o2Int == null) {
                return o1 - o2;
            } else {
                return o1Int == null ? o2Int : o1Int;
            }
        });

        int[] ans = new int[arr1List.size()];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = arr1List.get(i);
        }
        return ans;
    }


    public int[] relativeSortArray_s2(int[] arr1, int[] arr2) {

        if (arr1 == null || arr2 == null || arr1.length == 0) {
            return new int[0];
        }

        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr1.length; i++) {
            max = Math.max(max, arr1[i]);
        }

        int[] counter = new int[max + 1];
        for (int i = 0; i < arr1.length; i++) {
            ++counter[arr1[i]];
        }

        int[] ans = new int[arr1.length];
        int index = 0;
        for (int i = 0; i < arr2.length; i++) {
            while (counter[arr2[i]] != 0) {
                ans[index++] = arr2[i];
                --counter[arr2[i]];
            }
        }

        for (int i = 0; i < counter.length; i++) {
            while (counter[i] != 0) {
                ans[index++] = i;
                --counter[i];
            }
        }

        return ans;
    }

    @Test
    public void test01() {
        LeetCode1122 leetCode1122 = new LeetCode1122();
        int[] expect = leetCode1122.relativeSortArray_s1(new int[]{2, 21, 43, 38, 0, 42, 33, 7, 24, 13, 12, 27, 12, 24, 5, 23, 29, 48, 30, 31},
                new int[]{2, 42, 38, 0, 43, 21});
        Assert.assertArrayEquals(new int[]{2, 42, 38, 0, 43, 21, 5, 7, 12, 12, 13, 23, 24, 24, 27, 29, 30, 31, 33, 48}, expect);
    }
}
